1. Field of the Invention
The present invention relates to managing a computerized memory for storing data.
2. Description of Related Art
Solid-state memory devices encompass rewritable non-volatile memory devices which can use electronic circuitry for storing data. Currently, solid-state memory devices start replacing conventional storage devices such as hard disk drives and optical disk drives in some arenas, such as in mass storage applications for laptops or desktops. Solid state memory devices are also investigated for replacing conventional storage devices in other areas such as in enterprise storage systems. This is because solid state memory devices offer exceptional bandwidth as well as excellent random I/O (input/output) performance along with an appreciated robustness due to lack of moveable parts.
However, writing data to a solid-state memory device such as a flash memory device requires paying attention to specifics in the flash technology: NAND Flash memory is organized in units of pages and blocks. Multiple pages form a block. While read and write operations can be applied to pages as a smallest unit of such operation, erase operations can only be applied to entire blocks. And while in other storage technologies outdated data can simply be overwritten by new data, flash technology requires an erase operation before new data can be written to an erased block.
Because in flash technology erase operations take much longer than read or write operations, a writing technique is applied called “write out of place” in which new or updated data is written to some free page offered by a free page allocator instead of writing it to the same page where the outdated data resides. The page containing the outdated data is marked as invalid page.
At some point in time, a process called “garbage collection” frees blocks for new writes by moving the content of all valid pages of a block to free pages at one or more different blocks. As a result, the subject block finally comprises invalid pages only and can be erased. While this procedure requires some additional write operations in excess, it is apparent that by such approach immediate as well as frequent erase operations are avoided which would contribute to a much higher overall processing than an overhead of some additional write operations do.
The same mechanism applies to any memory structure in which new or updated data are written out-of-place, whereby data updates to outdated data are not written to the subunit containing the outdated data, but to a log which provides a series of free subunits where data is to be written to and where such subunits typically can not be subunits subsequent to each other in the organization of the storage device but can be scattered around the storage device and be offered by an allocation engine. Such systems can be referred to as log-structured file systems.
In the following, it can be referred to blocks instead of units, and to pages instead of subunits. Blocks and pages follow a nomenclature used in connection with flash-based solid-state storage devices. For the entire application it is understood that neither the content nor the scope of protection shall be restricted to the flash-based storage technology. Any other solid state storage technology such phase change memories, magnetic RAM memories, etc. shall be encompassed, too, as is any log structured file system making use of a storage device in a log-structured way.
The more data is written over time, the less free pages can be offered and new blocks can need to be reclaimed for a free block queue, i.e. a queue for providing free, i.e. erased blocks for writing new or updated data to. New free blocks need to be reclaimed from blocks filled with valid and/or invalid data. The block reclaiming process first identifies blocks for cleaning based on a given policy. Then valid data still residing in these blocks is copied (relocated) to other blocks, and finally the blocks that now are free from valid data are erased and become available again for rewriting. Consequently, the reclaiming mechanism introduces additional read and write operations, the extent of which depends on the specific policy deployed as well as on system parameters. The additional write operations result in the multiplication of user writes, a phenomenon referred to as “write amplification”. As the number of erase/write operations that can be performed before a solid state storage device wears out is limited, the extent of the write amplification is critical because it negatively affects the lifetime and endurance of solid state storage devices. Therefore, a reclaiming mechanism is efficient when it keeps the write amplification as low as possible, and also achieves a good wear leveling in the sense of blocks being worn out as evenly as possible.
In connection with log-structured file systems implemented on a hard disk reclaiming mechanisms are discussed. In “The Design and Implementation of a Log-Structured File System” by M. Rosenblum and J. Ousterhout, ACM Transactions on Computer Systems, Volume 10, No 1, pages 26-52, February 1992, a technique for disk storage management called a log-structured file system is introduced which writes all modifications to a disk sequentially in a log-like structure, thereby speeding up both file writing and crash recovery. The log is the only structure on the disk; it contains indexing information so that files can be read back from the log efficiently. In order to maintain large free areas on disk for fast writing, the log is divided into segments and uses a segment cleaner to compress the live information from heavily fragmented segments. One of the cleaners introduced uses a policy where it always chooses the least-utilized segments to clean.
When put in context with a flash-based solid state drive, the above policy introduces the usage of blocks only with the smallest number of valid pages for erasure, such that it yields the most amount of free space for reclaiming by means of a single action. As systems encountered in practice are comprised of thousands of blocks, the above reclaiming process would take a substantial amount of time to examine all of the blocks in order to select the block with the minimum amount of valid pages. This is also the case when the number of valid pages of blocks is constantly updated upon each host write. Depending on the processor's capabilities the time required can be prohibitively long.
To reduce the number of CPU cycles consumed by the such reclaiming process a windowed reclaiming scheme is proposed in “Write Amplification Analysis in Flash-Based Solid State Drives” by X.-Y. Hu, E. Eleftheriou, R. Haas, I. Iliadis, and R. Pletka, in Proceedings of the Israeli Experimental Systems Conference (SYSTOR), Haifa, Israel, pp. 1-9, Can 2009. According to this scheme, occupied blocks are maintained in a queue according to the order in which they have been written, with the oldest blocks occupying the first positions. The windowed reclaiming process restricts the selection process to the oldest w blocks only, which correspond to the first w positions in the queue as they are more likely to contain the least number of valid pages. As the window size w decreases, the number of CPU cycles consumed by the reclaiming process decreases, but the write amplification increases. The optimal choice of w requires knowledge of the overprovisioning factor of the system, which however can either not be available, or vary, i.e. not being constant during the lifetime of the device.